/*
题目链接：https://leetcode.cn/problems/count-of-integers/description/
	刘沛民	2024-12-3
*/

class Solution {
public:
    const int mod=1'000'000'007;
    int count(string num1, string num2, int min_sum, int max_sum) {
        int n=num2.size(),m=num1.size();
        num1=string(n-m,'0')+num1;
        vector<vector<int>>memo(n,vector<int>(min(9*n,max_sum)+1,-1));
        auto dfs=[&](auto&&dfs,int i,int sum,bool islower,bool ishigh)->int{
            if(sum>max_sum)return 0;
            if(i==n)return sum>=min_sum;
            if(!ishigh&&!islower&&memo[i][sum]!=-1)return memo[i][sum];
            int up=ishigh?num2[i]-'0':9;
            int low=islower?num1[i]-'0':0;
            int res=0;
            for(int d=low;d<=up;++d){
                res=(res+dfs(dfs,i+1,sum+d,islower&&d==low,ishigh&&d==up))%mod;
            }
            if(!ishigh&&!islower)memo[i][sum]=res;
            return res;
        };
        return dfs(dfs,0,0,true,true);
    }
};